package com.zp.self.module.level_4_算法练习.算法.位图;

/**
 * @author By ZengPeng
 */
public class 力扣_697_数组的度 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_697_数组的度().findShortestSubArray(new int[]{1,2,2,3,1}));
    }

    /**
    题目：给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
     你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

     示例 1：
     输入：nums = [1,2,2,3,1]
     输出：2
     解释：
     输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
     连续子数组里面拥有相同度的有如下所示：
     [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
     最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。

     示例 2：
     输入：nums = [1,2,2,3,1,4,2]
     输出：6
     解释：
     数组的度是 3 ，因为元素 2 重复出现 3 次。
     所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。

    分析：【P 💜💜】
       1.位图记录下标start 、end ,位图记录每个数个数  --50000 * 3 的内存：  1个数是 int  4 bit *50000 * 3 = 0.600 MB
            --执行用时：6 ms, 在所有 Java 提交中击败了95.61%的用户

    边界值 & 注意点：
       1.
     **/
    public int findShortestSubArray(int[] nums) {
        int[] count = new int[50000];
        int[] start = new int[50000];
        int[] end = new int[50000];
        int maxCount =0;
        for (int i = 0; i < nums.length; i++) {
            count[nums[i]]++;
            end[nums[i]]=i;
            if( count[nums[i]]>maxCount)
                maxCount= count[nums[i]];
            if(start[nums[i]]==0)
                start[nums[i]]=i;
        }
        start[nums[0]]=0;//因为前面0的判断原故，导致第一个数的start多移动了移除，重新将第一个位置标记为0
        int minLen=Integer.MAX_VALUE;
        for (int i = 0; i < end.length; i++) {
            if(count[i]==maxCount)
                minLen = Math.min(end[i]-start[i],minLen);
        }
        return minLen+1;
    }
}
